package tree.test99;

import listbyorder.utils.TreeNode;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/7/16 10:32
 */
public class Solution1 {

    public void recoverTree(TreeNode root) {
        // 首先进行边界条件判断
        if (root == null) return;

        // 计算出当前树左子树中的最大节点
        TreeNode maxLeft = getMaxNode(root.left);

        // 计算出当前树右子树中的最小的节点
        TreeNode minRight = getMinNode(root.right);

        // 情况一： 如果maxLeft.val > root.val && minRight.val < root.val ，则直接交换maxLeft 和 minRight 的节点值即可
        if (maxLeft != null && maxLeft.val > root.val && minRight != null && minRight.val < root.val) {
            int temp = maxLeft.val;
            maxLeft.val = minRight.val;
            minRight.val = temp;
            return;
        }

        // 情况二： 如果只有maxLeft.val > root.val， 交换maxLeft 和 root 节点的值
        if (maxLeft != null && maxLeft.val > root.val) {
            int temp = maxLeft.val;
            maxLeft.val = root.val;
            root.val = temp;
            return;
        }

        // 情况三： 如果只有minRight.val < root.val , 交换minRight 和 root 节点的值
        if (minRight != null && minRight.val < root.val) {
            int temp = minRight.val;
            minRight.val = root.val;
            root.val = temp;
            return;
        }

        // 情况四： 如果以上条件都不满足，左子树的节点可以发生了交换，递归至左子树
        recoverTree(root.left);

        // 情况五： 可能是右子树的节点发生了交换，递归至右子树
        recoverTree(root.right);
    }

    // 找到当前树中的最小值的节点
    private TreeNode getMinNode(TreeNode root) {
        if (root == null) return null;
        TreeNode left = getMinNode(root.left);
        TreeNode right = getMinNode(root.right);
        TreeNode min = root;
        if (left != null && left.val < min.val) {
            min = left;
        }
        if (right != null && right.val < min.val) {
            min = right;
        }
        return min;
    }

    // 找到当前树中的最大值的节点
    private TreeNode getMaxNode(TreeNode root) {
        if (root == null) return null;
        TreeNode left = getMaxNode(root.left);
        TreeNode right = getMaxNode(root.right);
        TreeNode max = root;
        if (left != null && left.val > max.val) {
            max = left;
        }
        if (right != null && right.val > max.val) {
            max = right;
        }
        return max;
    }
}
